import java.util.*;

public class Solution1994 {
    public int numberOfGoodSubsets(int[] nums) {
        int mod=1000000007;
        int[] f=new int[31];
        for (int num : nums) {
            f[num]++;
        }
        Set<Integer> bad=new HashSet<>(Arrays.asList(4,8,9,12,16,18,20,24,25,27,28));
        Map<Integer,Integer> map=new HashMap<>();
        map.put(2,0);
        map.put(3,1);
        map.put(5,2);
        map.put(7,3);
        map.put(11,4);
        map.put(13,5);
        map.put(17,6);
        map.put(19,7);
        map.put(23,8);
        map.put(29,9);
        long[] g=new long[(1<<10)];
        g[0]=1;
        for (int i=2;i<=30;i++){
            if (!bad.contains(i)&&f[i]>0){
                Set<Integer> set=new HashSet<>();
                for (int j=2;j<=i;j++) {
                    if (map.containsKey(j)&&i%j==0) {
                        set.add(map.get(j));
                    }
                }
                for (int k=(1<<10)-1;k>=0;k--){
                    int t=check(k,set);
                    if (t>=0){
                        g[k]=(g[k]+(g[t]*f[i]%mod))%mod;
                    }
                }
            }
        }
        long ans=0;
        for (int i=1;i<(1<<10);i++){
            ans=(ans+g[i])%mod;
        }
        int count=1;
        for (int i=0;i<f[1];i++){
            count=count*2%mod;
        }
        ans=(ans*count%mod);
        return (int)ans;
    }

    private int check(int k, Set<Integer> set) {
        int temp=k;
        for (Integer integer : set) {
            if ((temp&(1<<integer))>0){
                temp=(temp&(~(1<<integer)));
            }else {
                return -1;
            }
        }
        return temp;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1994().numberOfGoodSubsets(new int[]{5,10,1,26,21,23,11,17,2,6,1,1,6,13,30,2,19}));
    }
}
